//
// Description: 46. 全排列
// Created by Loading on 2021/8/15.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> permute(vector<int> &nums) {
    int n = nums.size();
    vector<vector<int>> res;

    function<void(int)> dfs = [&](int k) {
        if (k == n) {
            // 一种排列完成
            res.emplace_back(nums);
        } else {
            for (int i = k; i < n; ++i) {
                // 交换
                swap(nums[k], nums[i]);
                // 递归
                dfs(k + 1);
                // 回溯
                swap(nums[k], nums[i]);
            }
        }
    };

    dfs(0);

    return res;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    vector<vector<int>> res = permute(nums);
    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
}